#ifndef STX_ALGORITHM_PARTIAL_SORT_COPY_HPP
#define STX_ALGORITHM_PARTIAL_SORT_COPY_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/swap.hpp>
#include <stx/algorithm/make_heap.hpp>
#include <stx/algorithm/push_heap.hpp>
#include <stx/algorithm/sort_heap.hpp>

namespace stx {

template <class Compare, class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
partial_sort_copy_impl(
    InputIterator first,
    InputIterator last,
    RandomAccessIterator result_first,
    RandomAccessIterator result_last,
    Compare comp)
{
    RandomAccessIterator r = result_first;
    if (r != result_last) {
        typename std::iterator_traits<RandomAccessIterator>::difference_type len = 0;
        for (; first != last && r != result_last; ++first, ++r, ++len) {
            *r = *first;
        }
        make_heap_impl<Compare>(result_first, r, comp);
        for (; first != last; ++first) {
            if (comp(*first, *result_first)) {
                *result_first = *first;
                push_heap_front<Compare>(result_first, r, comp, len);
            }
        }
        sort_heap_impl<Compare>(result_first, r, comp);
    }
    return r;
}

template <class InputIterator, class RandomAccessIterator, class Compare>
inline RandomAccessIterator
partial_sort_copy(
    InputIterator first,
    InputIterator last,
    RandomAccessIterator result_first,
    RandomAccessIterator result_last,
    Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    return partial_sort_copy_impl<comp_ref>(first, last, result_first, result_last, comp);
}

template <class InputIterator, class RandomAccessIterator>
inline RandomAccessIterator
partial_sort_copy(
    InputIterator first,
    InputIterator last,
    RandomAccessIterator result_first,
    RandomAccessIterator result_last)
{
    return stx::partial_sort_copy(
        first,
        last,
        result_first,
        result_last,
        stx::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_PARTIAL_SORT_COPY_HPP
